package array;

import java.util.*;

public class J20210817 {
    //https://leetcode-cn.com/problems/3sum/
    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int length = nums.length;
        int a, b, c, d;
        List<List<Integer>> result = new ArrayList<>();

        for (int i = 0; i < length; i++) {
            a = nums[i];
            if (a > 0) {
                break;
            }

            int j = i + 1;
            int k = length - 1;
            if (j >= length - 1 || j > k) {
                break;
            }

            while (j < k) {
                b = nums[j];
                c = nums[k];
                d = a + b + c;

                if (d > 0) {
                    //while (k > 1 && nums[k] == c) k--;
                    //这种情况太少了
                    k--;
                } else if (d < 0) {
                    //while (k > 1 && nums[k] == c) k--;
                    j++;
                } else {
                    result.add(List.of(a, b, c));
                    while (j < k && nums[j] == b) j++;
                    while (k > 1 && nums[k] == c) k--;
                }
            }

            while (i + 1 < length - 1 && nums[i + 1] == a) {
                i++;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] test = new int[]{-4, -1, -1, 0, 1, 2};
        System.out.println(threeSum(test));
    }
}